//
//  Problem35.swift
//  TestProject 35. 搜索插入位置
//
//  Created by 武侠 on 2020/8/20.
//  Copyright © 2020 zhulong. All rights reserved.
//

import UIKit

/*
 35. 搜索插入位置： 二分法
 给定一个排序数组和一个目标值，在数组中找到目标值，并返回其索引。如果目标值不存在于数组中，返回它将会被按顺序插入的位置。

 你可以假设数组中无重复元素。

 示例 1:
 输入: [1,3,5,6], 5       输出: 2
 
 示例 2:
 输入: [1,3,5,6], 2       输出: 1
 
 示例 3:
 输入: [1,3,5,6], 7       输出: 4
 
 示例 4:
 输入: [1,3,5,6], 0       输出: 0
 */
@objcMembers class Problem35: NSObject {
    func solution() {
        
        print(searchInsert([1,3,5,6], 0))
    }
    
    // 只要找到第一个 >= target的位置就行
    func searchInsert(_ nums: [Int], _ target: Int) -> Int {
        var s = 0
        var e = nums.count - 1
        var mid = 0
        while s <= e {
            mid = (e - s) / 2 + s
            if nums[mid] < target {
                s = mid + 1
            } else {
                e = mid - 1
            }
        }
        return s
    }
}
